package com.leetcode.BinaryTree;

import com.sun.source.tree.Tree;

public class lc_230 {
    public static void main(String[] args) {

    }

    //给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。
    //思路:二叉搜索树的第k个元素就是中序遍历的第k个元素
    //定义全局变量
    int res, k;
    public int kthSmallest(TreeNode root, int k){
        //1.判断,返回参数为int,当前进行的第k次递归就是第k小的元素
        this.k = k;
        dfs(root);
        return res;
    }

    public void dfs(TreeNode root){
        //2.边界条件:root==null,直接return,
        if (root == null) return;
        //3.每一层逻辑:先遍历左节点,然后进行判断,如果k=0,说明是中序遍历的第k个元素
        dfs(root.left);
        if(k == 0) return;
        //先将k-1,再判断k是否等于0,如果等于0说明是第k小元素,用res留存
        if(--k == 0) res = root.val;
        dfs(root.right);
    }
}
